数据结构(C语言版 第2版)课后习题答案 严蔚敏版 |
您所在的位置:网站首页 › rear l › 数据结构(C语言版 第2版)课后习题答案 严蔚敏版 |
数据结构(C语言版 第2版)课后习题答案 严蔚敏 等 编著,仅供参考,还是自己认真做了再看 第1章 绪论
5.选择题 (1)在数据结构中,从逻辑上可以把数据结构分成( C )。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 (2)与数据元素本身的形式、内容、相对位置、个数无关的是数据的( C )。 A.存储结构 B.存储实现 C.逻辑结构 D.运算实现 (3)通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着( B )。 A.数据具有同一特点 B.不仅数据元素所包含的数据项的个数要相同,而且对应数据项的类型要一致 C.每个数据元素都一样 D.数据元素所包含的数据项的个数要相等 (4)以下说法正确的是( D )。 A.数据元素是数据的最小单位 B.数据项是数据的基本单位 C.数据结构是带有结构的各数据项的集合 D.一些表面上很不相同的数据可以有相同的逻辑结构 解释:数据元素是数据的基本单位,数据项是数据的最小单位,数据结构是带有结构的各数据元素的集合。 (5)算法的时间复杂度取决于( D )。 A.问题的规模 B.待处理数据的初态 C.计算机的配置 D.A和B 解释:算法的时间复杂度不仅与问题的规模有关,还与问题的其他因素有关。如某些排序的算法,其执行时间与待排序记录的初始状态有关。为此,有时会对算法有最好、最坏以及平均时间复杂度的评价。 (6)以下数据结构中,( A )是非线性数据结构 A.树 B.字符串 C.队列 D.栈
6.试分析下面各程序段的时间复杂度。 (1)x=90; y=100; while(y>0) if(x>100) {x=x-10;y--;} else x++; 答案:O(1) 解释:程序的执行次数为常数阶。 (2)for (i=0; inext=p->next; p->next=s; 答案:D (14) 在双向链表存储结构中,删除p所指的结点时须修改指针( )。 A.p->next->prior=p->prior; p->prior->next=p->next; B.p->next=p->next->next; p->next->prior=p; C.p->prior->next=p; p->prior=p->prior->prior; D.p->prior=p->next->next; p->next=p->prior->prior; 答案:A (15) 在双向循环链表中,在p指针所指的结点后插入q所指向的新结点,其修改指针的操作是( )。 A.p->next=q; q->prior=p; p->next->prior=q; q->next=q; B.p->next=q; p->next->prior=q; q->prior=p; q->next=p->next; C.q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; D.q->prior=p; q->next=p->next; p->next=q; p->next->prior=q; 答案:C 2.算法设计题 (1)将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。 [题目分析] (合并后的新表用一个新的Lc指针。新建一个Lc头指针,pa和pb分别是链表La和Lb的工作指针且初始化为相应链表的第一个结点。从第一个结点开始进行比较,当两个链表La和Lb均未到达表尾结点时,则依次摘取较小元素重新链接在Lc表的后面。其中,如果两个表中的元素相等,只摘取La表中的元素,删除Lb表中的元素(注意释放删除的元素的空间),这样确保合并后表中无重复的元素。当一个表到达表尾结点,为空时,将非空表的剩余元素直接链接在Lc表的最后面。 [算法描述] void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) {//合并链表La和Lb,合并后的新表使用头指针Lc指向 pa=La->next; pb=Lb->next; //pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa && pb) { if(pa->datadata){ pc->next=pa; pc=pa; pa=pa->next; } //取较小者La中的元素,将pa链接在pc的后面,pa指针后移 else if(pa->data>pb->data){ pc->next=pb; pc=pb; pb=pb->next; } //取较小者Lb中的元素,将pb链接在pc的后面,pb指针后移 else //相等时取La中的元素,删除Lb中的元素 { pc->next=pa; pc=pa; pa=pa->next; q=pb->next;delete pb ;pb =q;(删除记得要释放空间) //q=pb;pb=q->next;delete q; } } pc->next=pa?pa:pb; //插入剩余段 delete Lb; //释放Lb的头结点(La的头结点已赋给了Lc,不需释放) } (2)将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。
[题目分析] 合并后的新表使用头指针Lc指向,pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点,从第一个结点开始进行比较,当两个链表La和Lb均为到达表尾结点时,依次摘取其中较小者重新链接在Lc表的表头结点之后,如果两个表中的元素相等,只摘取La表中的元素,保留Lb表中的元素。当一个表到达表尾结点,为空时,将非空表的剩余元素依次摘取,链接在Lc表的表头结点之后(前插法)。 [算法描述] void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, ) {//合并链表La和Lb,合并后的新表使用头指针Lc指向 pa=La->next; pb=Lb->next; //pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 Lc=pc=La; //用La的头结点作为Lc的头结点 Lc->next=NULL; while(pa||pb) {//只要存在一个非空表,用q指向待摘取的元素 if(!pa) {q=pb; pb=pb->next;} //La表为空,用q指向pb,pb指针后移 else if(!pb) {q=pa; pa=pa->next;} //Lb表为空,用q指向pa,pa指针后移 else if(pa->datadata) {q=pa; pa=pa->next;} //取较小者(包括相等)La中的元素,用q指向pa,pa指针后移 else {q=pb; pb=pb->next;} //取较小者Lb中的元素,用q指向pb,pb指针后移 q->next = Lc->next; Lc->next = q; //将q指向的结点插在Lc 表的表头结点之后 } delete Lb; //释放Lb的头结点 }
(3)已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出A与B的交集,并存放于A链表中。 [题目分析] 只有同时出现在两集合中的元素才出现在结果表中,合并后的新表使用头指针Lc指向。pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点,从第一个结点开始进行比较,当两个链表La和Lb均为到达表尾结点时,如果两个表中相等的元素时,摘取La表中的元素,删除Lb表中的元素;如果其中一个表中的元素较小时,删除此表中较小的元素,此表的工作指针后移。当链表La和Lb有一个到达表尾结点,为空时,依次删除另一个非空表中的所有元素。 [算法描述] void Mix(LinkList& La, LinkList& Lb, LinkList& Lc) { pa=La->next;pb=Lb->next; pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa&&pb) { if(pa->data==pb->data)∥交集并入结果表中。 { pc->next=pa;pc=pa;pa=pa->next; u=pb;pb=pb->next; delete u;} else if(pa->datadata) {u=pa;pa=pa->next; delete u;} else {u=pb; pb=pb->next; delete u;} } while(pa) {u=pa; pa=pa->next; delete u;}∥ 释放结点空间 while(pb) {u=pb; pb=pb->next; delete u;}∥释放结点空间 pc->next=null;∥置链表尾标记。 delete Lb; //释放Lb的头结点 }
(4)已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出两个集合A和B 的差集(即仅由在A中出现而不在B中出现的元素所构成的集合),并以同样的形式存储,同时返回该集合的元素个数。 [题目分析] 求两个集合A和B的差集是指在A中删除A和B中共有的元素,即删除链表中的相应结点,所以要保存待删除结点的前驱,使用指针pre指向前驱结点。pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点,从第一个结点开始进行比较,当两个链表La和Lb均为到达表尾结点时,如果La表中的元素小于Lb表中的元素,pre置为La表的工作指针pa删除Lb表中的元素;如果其中一个表中的元素较小时,删除此表中较小的元素,此表的工作指针后移。当链表La和Lb有一个为空时,依次删除另一个非空表中的所有元素。 [算法描述] void Difference(LinkList& La, LinkList& Lb,int *n) {∥差集的结果存储于单链表La中,*n是结果集合中元素个数,调用时为0 pa=La->next; pb=Lb->next; ∥pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 pre=La; ∥pre为La中pa所指结点的前驱结点的指针 while(pa&&pb) {if(pa->datadata){pre=pa;pa=pa->next;*n++;} ∥ A链表中当前结点指针后移 else if(pa->data>q->data)q=q->next; ∥B链表中当前结点指针后移 else {pre->next=pa->next; ∥处理A,B中元素值相同的结点,应删除 u=pa; pa=pa->next; delete u;} ∥删除结点 } }
(5)设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C,其中B表的结点为A表中值小于零的结点,而C表的结点为A表中值大于零的结点(链表A中的元素为非零整数,要求B、C表利用A表的结点)。 [题目分析] B表的头结点使用原来A表的头结点,为C表新申请一个头结点。从A表的第一个结点开始,依次取其每个结点p,判断结点p的值是否小于0,利用前插法,将小于0的结点插入B表,大于等于0的结点插入C表。 [算法描述] void DisCompose(LinkedList A) { B=A; B->next= NULL; ∥B表初始化 C=new LNode;∥为C申请结点空间 C->next=NULL; ∥C初始化为空表 p=A->next; ∥p为工作指针 while(p!= NULL) { r=p->next; ∥暂存p的后继 if(p->datanext=B->next; B->next=p; }∥将小于0的结点链入B表,前插法 else {p->next=C->next; C->next=p; }∥将大于等于0的结点链入C表,前插法 p=r;∥p指向新的待处理结点。 } }
第3章 栈和队列 1.选择题 (1)若让元素1,2,3,4,5依次进栈,则出栈次序不可能出现在( )种情况。 A.5,4,3,2,1 B.2,1,5,4,3 C.4,3,1,2,5 D.2,3,5,4,1 答案:C 解释:栈是后进先出的线性表,不难发现C选项中元素1比元素2先出栈,违背了栈的后进先出原则,所以不可能出现C选项所示的情况。 (2)若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为( )。 A.i B.n-i C.n-i+1 D.不确定 答案:C 解释:栈是后进先出的线性表,一个栈的入栈序列是1,2,3,…,n,而输出序列的第一个元素为n,说明1,2,3,…,n一次性全部进栈,再进行输出,所以p1=n,p2=n-1,…,pi=n-i+1。 (3)数组Q[n]用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素个数的公式为( )。 A.r-f B.(n+f-r)%n C.n+r-f D.(n+r-f)%n 答案:D 解释:对于非循环队列,尾指针和头指针的差值便是队列的长度,而对于循环队列,差值可能为负数,所以需要将差值加上MAXSIZE(本题为n),然后与MAXSIZE(本题为n)求余,即(n+r-f)%n。 (4)链式栈结点为:(data,link),top指向栈顶.若想摘除栈顶结点,并将删除结点的值保存到x中,则应执行操作( )。 A.x=top->data;top=top->link; B.top=top->link;x=top->link; C.x=top;top=top->link; D.x=top->link; 答案:A 解释:x=top->data将结点的值保存到x中,top=top->link栈顶指针指向栈顶下一结点,即摘除栈顶结点。 (5)设有一个递归算法如下 int fact(int n) { //n大于等于0 if(n |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |